/*
 * ForwardDawgMatching.cpp
 *
 *  Created on: 02-09-2013
 *      Author: Krzychu
 */

#include "ForwardDawgMatching.h"

#include "Config.h"
#include "SuffixAutomaton.h"

#define ASIZE 255

ForwardDawgMatching::ForwardDawgMatching()
{

}

ForwardDawgMatching::~ForwardDawgMatching()
{

}

std::string ForwardDawgMatching::getName()
{
	return "Forward Dawg Matching";
}

searchResult ForwardDawgMatching::execute(std::string text, std::string pattern)
{
	searchResult result;
	result.iterationsTaken = 0;

	int textSize = text.size();
	int patternSize = pattern.size();

	/* Preprocessing */
	SuffixAutomaton* aut = new SuffixAutomaton(2 * (patternSize + 2), 2 * (patternSize + 2) * ASIZE);
	buildSuffixAutomaton(pattern, aut);
	int init = aut->getInitial();

	/* Searching */
	int ell = 0;
	int state = init;
	for (int j = 0; j < textSize; ++j)
	{
		result.iterationsTaken++;

		if (aut->getTarget(state, text[j]) != aut->getUndefined())
		{
			++ell;
			state = aut->getTarget(state, text[j]);
		}
		else
		{
			while (state != init && aut->getTarget(state, text[j]) == aut->getUndefined())
			{
				state = aut->getSuffixLink(state);
			}
			if (aut->getTarget(state, text[j]) != aut->getUndefined())
			{
				ell = aut->getLength(state) + 1;
				state = aut->getTarget(state, text[j]);
			}
			else
			{
				ell = 0;
				state = init;
			}
		}
		if (ell == patternSize)
		{
			result.positionsFound.push_back(j - patternSize + 1);
			if (Config::getInstance()->getFindOneOccurence())
			{
				return result;
			}
		}
	}

	return result;
}

